import java.util.*;

import static java.lang.Math.*;


/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 25397
 * Date: 2022-03-21
 * Time: 19:15
 */

public class Main {

    //day2
    //将一句话的单词进行倒置，标点不倒置，比如i like beijing. 倒置后变成beijing. like i
    //标准答案
//    public static void nz(char[] arr,int start,int end) {//字符串逆置
//        while(start<end) {
//            char tmp=arr[start];
//            arr[start]=arr[end];
//            arr[end]=tmp;
//            start++;
//            end--;
//        }
//    }
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        String str=scanner.nextLine();
//        char[]ch=str.toCharArray();//字符串转字符数组函数
//        nz(ch,0,str.length()-1);//先整体逆置一下，比如i like you 变成uoy ekil i
//        int i=0;
//        while(i<str.length()){
//            int j=i;
//            while(j<str.length()&&ch[j]!=' '){
//                j++;
//            }
//            if(j<str.length()){
//                nz(ch,i,j-1);
//                i=j+1;
//            }else{
//                nz(ch,i,j-1);
//                i=j;
//            }
//        }
//        String str2=new String(ch);
//        System.out.println(str2);
//
//    }


    //在一行中输出str中连续最长的数字串(正确)
    //eg:输入str：abcd12345de125ss123456789
    //输出：123456789
//    public static void main(String[] args) {
//
//        Scanner scanner=new Scanner(System.in);
//        String str=scanner.nextLine();
//
//
//        int bj=0;//标记一个数字串长度，0代表结束，1代表开始
//        int max=0;//max是最大长度，最后可以通过max 遍历,也就是数字串开始位置->数字串开始位置+max
//        int ks=0;//标记每次数字串开始位置
//        int maxKs=0;//最长字符串开始位置
//        for(int i=0;i<str.length();i++){
//            //遍历到数字
//            if(48<=str.charAt(i)&&str.charAt(i)<=57){
//                bj++;
//                if(bj==1){//每次数字串第一个位置
//                    ks=i;
//                }
//                if(max<bj){//新的最长出现
//                    max=bj;
//                    maxKs=i-max;
//                }
//            }else{//遍历到非数字
//                bj=0;
//            }
//        }
//
//        for(int i=maxKs+1;i<=maxKs+max;i++){
//            System.out.print(str.charAt(i));
//        }
//    }


    //给一个长度为n的数组，数组内有一个数字出现的次数超过了数组长度的一半，请找出这个数字
    //eg:[1,2,3,2,2,2,5,4,2]
    //2在数组中出现了5次，超过数组长度一半，输出2
    //eg:[1],输出1
//    public int MoreThanHalfNum_Solution(int [] array) {
//        if(array.length==1){
//            return array[0];
//        }
//        int mid=array.length/2;
//        int max=0;
//        HashMap<Integer,Integer> hashMap=new HashMap<>();
//        for(int i=0;i<array.length;i++){
//            if(hashMap.get(array[i])!=null){
//                int tmp=hashMap.get(array[i]);
//                if(tmp+1>mid){
//                  max=array[i];
//                }
//                hashMap.put(array[i],tmp+1);
//            }else{
//                hashMap.put(array[i],1);
//            }
//        }
//        return max;
//    }


    //day5
    //A,B,C三人是好友，每个人手里都有一些糖果，我们不知道每人具体有多少糖果
    //但是我们知道A-B,B-C,A+B,B+C这四个数值，代表每个人拥有的糖果数
    //输入为：A-B,B-C,A+B,B+C，用空格隔开（范围均在-30~30）
    //输出为1行，如果存在满足的数A,B,C则按顺序输出A,B,C，用空格隔开，行末无空格
    //如果不存在这样的整数A,B,C则输出No
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        int x0 = 0,x1=0,x2=0,x3=0;//表示A-B,B-C,A+B,B+C四个数
//        int i=0;
//        while(scanner.hasNext()){
//            x0=scanner.nextInt();
//            x1=scanner.nextInt();
//            x2=scanner.nextInt();
//            x3=scanner.nextInt();
//            int A=(x0+x2)/2;
//            int B=(x1+x3)/2;
//            int C=(x3-x1)/2;
//
//            //糖果按颗算，应该是整数
//            if(A-((x0+x2)/2)!=0){//如果A是浮点数，减去整形的(x[0]+x[2])/2不会为0
//                System.out.println("No");
//                return;
//            }
//
//            if(B-((x1+x3)/2)!=0||B-((x2-x0)/2)!=0){
//                System.out.println("No");
//                return;
//            }
//
//            if(C-(x2-x1-A)!=0){
//                System.out.println("No");
//                return;
//            }
//
//            System.out.println(A+" "+B+" "+C);
//
//        }
//    }


//    给定一个十进制数M，以及需要转换的进制数N，将十进制数M，转换成N进制数
//    输入为一行，M是(32)位整数，N（2<=N<=16），用空格隔开
//
//    eg:输入 7 2
//       输出 111
//
//    输出描述：为了每个测试实例输出转换后的数，每个输出占一行。
//    如果N大于9，则对应的数字规则参考16进制（比如10用A表示，等等）
//    public static void main(String[] args) {//标准答案
//        Scanner scanner=new Scanner(System.in);
//        int m=scanner.nextInt();
//        int n=scanner.nextInt();
//        boolean b=true;//true表示是正数，防止m输过来的是负数，
//        if(m<0) {
//            m=-m;
//            b=false;
//        }
//
//        String str="";//用来放m每个位的数
//        String table="0123456789ABCDEFG";//用m%n来标记table下标，获取相应值
//        while((m/n)!=0) {//获取m每个位的数
//            str+=table.charAt(m%n);
//            m=m/n;
//        }
//        str+=m%n;
//
//        String str2="";//将str逆置
//        for(int i=str.length()-1;i>=0;i--) {
//            str2+=str.charAt(i);
//        }
//        if(b==false) {
//            str2="-"+str2;
//        }
//        System.out.print(str2);
//
//    }


    //3.25
    //回文串是一个正读反读都一样的字符串，比如“level”或者“noon”
    //现给字符串A和字符串B，请问有没有办法将B插入A中，使得产生新字符串是一个回文串
    //比如A="aba",B="b"
    //插法1(插第一个a前面)：“baba” 不是回文串
    //插法2(插第一个a后面)：“abba” 是回文串
    //插法3(插第一个b后面)：“abba” 是回文串
    //插法4(插第二个a后面)：“abab” 不是回文串

    //输入：每组输入数据共两行，第一行为字符串A，第二行为字符串B（字符串长度均小于100，且只包含小写字母)
    //输出一个数字，表示把B插入A之后构成一个回文串的方法数，比如上面例子，会输出2
//    public static boolean isHwc(String str){//判断是否是回文串
//        int x=str.length()/2;
//        for(int i=0;i<x;i++){
//            if(str.charAt(i)!=str.charAt(str.length()-1-i)){//str.length()-1是最后下标，然后再-i才与前面对应
//                return false;
//            }
//        }
//        return true;
//    }
//    public static void main(String[] args) {//(案例已全部通过)
//        Scanner scanner=new Scanner(System.in);
//        String A=scanner.nextLine();;
//        String B=scanner.nextLine();;
//        int k=0;//标记构成回文串的次数
//        String tmp="";//tmp表示A第i个字符串前面的字符串(不包括第i个字符)，比如A：abcdef，i=3,那么tmp=ab
//
//        for(int i=1;i<=A.length();i++){//把B插入A
//
//            if(i>=2){//这里i>=2是为了保证tmp不包括第i个字符串
//                tmp=tmp+A.charAt(i-2);//i是从2开始的，所以要-2
//            }
//
//            if(i==1){//插第一个字母前:B+A
//                String C=B+A;
//                if(isHwc(C)){
//                    k++;
//                }
//            }
//            //插第i个字母前：(i>1)
//            if(1<i&&i<=A.length()){
//                String D="";//D表示A第i个字符串后面的字符串(包括第i个字符)
//                for(int j=i-1;j<A.length();j++){
//                    D=D+A.charAt(j);
//                }
//                String C=tmp+B+D;
//                if(isHwc(C)){
//                    k++;
//                }
//            }
//        }
//        //插最后一个字母后
//        String C=A+B;
//        if(isHwc(C)){
//            k++;
//        }
//        System.out.println(k);
//    }

//    一个数组有N个元素，求连续子数组的最大和。
//    例如：[-1,2,1]，和最大的连续子数组为[2,1],其和为3
//
//    输入：第一行一个整数n(1<=n<=100000),表示一个有n个元素
//         第二行为n个数，即每个元素，每个整数在32位int范围内，以空格分隔
//    例如输入3
//          -1 2 1
//    输出3

//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        int n=scanner.nextInt();
//        int[]arr=new int[n];
//        for(int i=0;i<n;i++) {
//            arr[i]=scanner.nextInt();
//        }
//
//        int sum=arr[0];
//        int max=arr[0];
//        for(int i=1;i<n;i++) {
//            if(sum+arr[i]>arr[i]){
//                sum+=arr[i];
//            }else{
//                sum=arr[i];
//            }
//
//            if(sum>max) {
//                max=sum;
//            }
//        }
//        System.out.print(max);
//    }


    //3.26
//    二货小易现有一个W*H的网格盒子，网格的行编号为0~H-1，网格的列编号为0~W-1。
//    每个格子可放1块蛋糕，任意两块蛋糕的欧几里得距离不能等于2
//    对于两个格子坐标(x1,y1),(x2,y2)的欧几里得距离为：
//    [(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)]的平方根
//    小易想知道最多可放多少块蛋糕在网格盒子里
//
//    输入：每组数组包含网格长宽W,H,用空格分割（1<=W、H<=1000）
//    输出：最多可以放的蛋糕数

//        public static void main(String[] args){
//            Scanner scanner=new Scanner(System.in);
//            int w=scanner.nextInt();
//            int h=scanner.nextInt();
//            int count=0;
//            int[][]arr=new int[w][h];
//            //数组默认里面为0，那我们规定为0可以放，为1不可以放
//            for(int i=0;i<w;i++) {
//                for(int j=0;j<h;j++) {
//                    if(arr[i][j]==0) {
//                        count++;
//                        if(i+2<w) {//防止越界
//                            arr[i+2][j]=1;
//                        }
//                        if(j+2<h) {
//                            arr[i][j+2]=1;
//                        }
//                    }
//                }
//            }
//            System.out.print(count);
//        }


    //将一个字符串转换成一个整数，要求不能使用字符串转换成整数的库函数
    //数值为0或者字符串不是一个合法的数值则返回0

    //数据范围：字符串长度0<=n<=100
    //进阶：空间复杂度O（1），时间复杂度O（n)

    //注意：
    //1.字符串中可能出现任意符号，出现除+/-以外的符号直接输出0
    //2.字符串中可能出现+/-且仅可能出现在字符串首位
    //输入：输入一个字符串，包括数字字母符号，可以为空
    //如果是合法的数值表达则返回该数字，否则返回0

    //eg:输入"+2147483647"
    //   输出2147483647

    //   输入“-123”
    //   输出“-123”

    //eg:输入"1a33"
    //   输出0
//    public static int StrToInt(String str) {//通过
//        ArrayList<Integer> arrayList = new ArrayList<>();
//        int bj = 0;//标记数字一共多少位
//        boolean b=true;//true表示正，false表示负
//        for (int i = 0; i < str.length(); i++) {
//            if (57 < str.charAt(i) || str.charAt(i) < 48) {//非数字情况
//                if (str.charAt(i) == '+' || str.charAt(i) == '-') {
//                    if(str.charAt(0)=='-'){
//                        b=false;
//                    }
//                    continue;
//                }
//                return 0;
//            } else {//是数字
//                arrayList.add((int) (str.charAt(i)) - 48);
//                bj++;
//            }
//        }
//        int f = 0;
//        //int bj2=0;//表示10的几次方，比如123=1*10^2+2*10^1+3*10^0
//        for (int i = 0; i < bj; i++) {
//            f = f + arrayList.get(bj - 1 - i) * (int) pow(10, i);
//        }
//        if(b==false){
//            f=-f;
//        }
//        return f;
//    }
//
//    public static void main(String[] args) {
//        int ret = StrToInt("-214");
//        System.out.println(ret);
//
//    }

    //3.27
    //Fibonacci数列是这样定义的：F[0]=0,F[1]=1
    //i>=2,F[i]=F[i-1]+F[i-2]
    //因此，Fibonacci数列就形如：0，1，1，2，3，5，8，13，21...
    //给你一个N,你想让其变成一个Fibonacci数，每一步你可以把当前数X变为X-1或者X+1
    //现给你一个数N，求最少多少步可以变成Fibonacci数

    //输入描述：输入为一个正整数(1<=N<=1,000,000)
    //输出描述：输出一个变为Fibonacci数的最小步数

    //eg:输入15，输出2
//    public static void main(String[] args) {//通过
//        Scanner scanner=new Scanner(System.in);
//        int n=scanner.nextInt();
//
//        //可以边生成斐波那契数，边判断n
//        //n一定是在某两个个斐波那契数中间（包含边界）
//        int x=0;//表示F[i-2]
//        int y=1;//表示F[i-1]
//        int z=1;//表示F[i]
//        while(true){
//            if(n==z){//n范围[1,1000000]
//                System.out.println(0);
//                return;
//            }
//            if(n>z){
//                z=y+z;
//                int tmp=y;
//                y=x+y;
//                x=tmp;
//            }
//            if(n<z){
//                System.out.println((n-y)<(z-n)?n-y:z-n);
//                return;
//            }
//        }
//    }


    //给定一个字符串A和长度n，请返回一个bool值代表它是否是一个合法的括号串（只能由括号组成）
    //测试样例：
    //"((()())",6
    //true

    //"()a()()",7
    //false

    //"()(()()",7
    //false
//    public boolean chkParenthesis(String A, int n) {//通过
//        int bj1=0;//标记“(”的个数
//        int bj2=0;//标记“)”的个数
//        for(int i=0;i<A.length();i++){
//            if(A.charAt(i)=='('){
//                bj1++;
//            }
//            if(A.charAt(i)==')'){
//                bj2++;
//            }
//        }
//        if(bj1!=bj2){
//            return false;
//        }
//        return true;
//    }

    //3.28
    //考拉有n个字符串，任意两个字符串长度都是不同的。考拉最近学习到两种字符串的排序方法：
    //1.根据字符串的字典序排序。eg："cat"<"carriage"<"cats"<"doggies"<"koala"
    //2.根据字符串的长度排序。eg:"cat"<"cats"<"koala"<"doggies"<"carriage"
    //考拉想知道自己这些字符串排列顺序是否满足这两种排序方法，考拉要忙着吃树叶，所以你来帮忙验证

    //输入：输入第一行为字符串的个数n（n<=100）
    //接下来的n行，每行一个字符串，字符串长度均小于100，均由小写字母组成

    //输出：如果这些字符串根据字典序排列,但不是根据长度排列，输出“lexicographically”
    //     如果这些字符串根据长度排列，但不是根据字典序排列，输出“lengths”
    //     如果两种方式都符合，输出“both”
    //     如果不是字典序排列，也不是长度排列，输出“none”
//    public static boolean isLengths(String[] str){//判断是不是按长度排列
//        for(int i=0;i< str.length-1;i++){
//            if(str[i].length()>str[i+1].length()){
//                return false;
//            }
//        }
//        return true;
//    }
//
//    //判断两个字符串是不是字典序排列——str1是不是在字典中是在str2前面
//    public static boolean isLex(String str1,String str2){
//        //字典序的话字母相同也是要分长度的：比如car<carriage
//        int l=min(str1.length(),str2.length());//找出str1和str2中较小长度（不能找较大长度，否则小的那个会越界）
//        for(int i=0;i<l;i++){
//            if(str1.charAt(i)<str2.charAt(i)){
//                return true;
//            }
//            if(str1.charAt(i)>str2.charAt(i)){
//                return false;
//            }
//        }
//        //走到这里没有return 说明前面一部分字母都是相同的
//        //但是car在字典中不能排在carriage后——也就是str1=="carriage",str2=="car"不能直接返回true
//        if(str1.charAt(l-1)==str2.charAt(l-1)){
//            //不能直接if(str1.length()>str2.length())
//            //有可能出现carriage 和 cats这种情况，本来是字典序没问题，
//            // 但是前者长度大于后者会进入里面的if，你直接return false就错了，所以外层套一个if，判断末尾结束字符是否一样
//            if(str1.length()>str2.length()){
//                return false;
//            }
//        }
//        return true;
//    }
//
//    public static boolean isLexicographically(String[] str){//判断是不是字典序排列
//        int k=0;//标记对比次数，如果要return true,需要全部对比完
//        // 比如字符串组str中有3个，你要对比1和2,2和3，共对比2次。如果str中有n个，要对比n-1次
//        for(int i=0;i<str.length-1;i++){
//            if(isLex(str[i],str[i+1])){
//                k++;
//                if(k==str.length-1){
//                    return true;
//                }
//            }else{
//                break;//进入else说明上面isLex返回的是false，也就是：不是字典排序
//            }
//        }
//        return false;
//    }
//
//    public static void main(String[]args){
//        Scanner scanner=new Scanner(System.in);
//        int n=scanner.nextInt();
//        scanner.nextLine();//把n产生的回车回收一下
//
//        String[] arr=new String[n];
//        int x=0;//标记是不是按长度排列，不是——x=0，是——x=1
//        int y=0;//标记是不是按字典序排列，不是——y=0，是——y=1
//
//        for(int i=0;i<n;i++){
//            arr[i]=scanner.nextLine();
//        }
//
//        if(isLengths(arr)){
//            x=1;
//        }
//        if(isLexicographically(arr)){
//            y=1;
//        }
//
//        if(y==1&&x==0){//根据字典序排列,但不是根据长度排列
//            System.out.println("lexicographically");
//        }
//        if(y==0&&x==1){//根据长度排列,但不是根据字典序排列
//            System.out.println("lengths");
//        }if(y==1&&x==1){//都是
//            System.out.println("both");
//        }if(y==0&&x==0){//都不是
//            System.out.println("none");
//        }
//    }


    //3.30
    //给定两个int A，B 编写一个函数返回A+B的值，但不得使用+或者其他算数运算符
    //参考答案
//    public static int addAB(int A, int B) {
//        int sum;
//        int c;
//        while(B!=0){
//            sum=A^B;
//            c=(A&B)<<1;
//            A=sum;
//            B=c;
//        }
//        return A;
//    }
//
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        int A=scanner.nextInt();
//        int B=scanner.nextInt();
//        System.out.println(addAB(A,B));
//    }


//    请计算n*m的棋盘格子(n为横向的格子数，m为竖向的格子数），从棋盘左上角出发
//    沿着边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路
//    即：只能往右和往下走，不能往左和往上走
//    注：沿棋盘格之间的边缘线走
//
//    数据范围：1<=n,m<=8
//
//    输入描述：输入两个正整数n和m，用空格隔开
//    输出描述：输出结果

    //通过
//    public static int gz(int x,int y){//xy表示行和列
//        if((x==1&&y==2)||(x==2&&y==1)){//1*2和2*1都是只有3种走法
//            return 3;
//        }
//        if(x==1&&y==1){//1*1是2种走法
//            return 2;
//        }
//        if(x==0||y==0){//走到最右边或最下边，就只能直着走了
//            return 1;
//        }
//        return gz(x,y-1)+gz(x-1,y);//向右递归和向下递归
//
//    }
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        int n=scanner.nextInt();//列
//        int m=scanner.nextInt();//行
//        System.out.println(gz(m,n));
//
//    }


    //3.31
    //给定一个二维数组board，代表棋盘，其中元素为1的代表是当前玩家的棋子，
    //0表示没有棋子，-1表示对方玩家棋子。
    //当一方棋子在横竖斜方向有连城排的获胜（井字棋规则）
    //返回当前玩家是否胜出

    //eg:[[1,0,1],[1,-1,-1],[1,-1,0]]
    //返回true
//    public boolean checkWon(int[][] board) {//通过
//         int h= board.length;//棋盘的行
//         int l=board[0].length;//棋盘的列
//
//        for(int i=0;i<h;i++){//判断是否有一列 结束游戏
//            int tmp=board[i][0]; //如果是行结束游戏，那这行的数都应该相同
//                int bj=0;//标记相同棋子个数
//                for(int j=0;j<l;j++){
//                    if(board[i][j]!=tmp){
//                        break;
//                    }else{
//                        bj++;
//                        if(bj==l){//该行结束游戏
//                            return tmp==1?true:false;
//                        }
//                    }
//                }
//        }
//
//        for(int j=0;j<l;j++){//判断是否有一行 结束游戏
//            int tmp=board[0][j];
//
//                int bj=0;
//                for(int i=0;i<h;i++){
//                    if(board[i][j]!=tmp){
//                        break;
//                    }else{
//                        bj++;
//                        if(bj==h){//该行结束游戏
//                            return tmp==1?true:false;
//                        }
//                    }
//                }
//        }
//
//        //判断是否是右斜线 结束游戏
//        //从左上角开始判断
//
//            int i=0,j=0;
//            int bj=0;//标记行数
//            while (i<h-1&&j<l-1){
//                if(board[i][j]!=board[i+1][j+1]){
//                    break;
//                }else{
//                    i++;
//                    j++;
//                    bj++;
//                    if(bj==h-1){
//                        return board[i][j]==1?true:false;
//                    }
//                }
//            }
//
//
//
//        //判断是否左斜线，结束游戏
//        //从右上角开始判断
//
//           bj=0;//标记行数
//            while(h-1>=1&&l-1>=1){
//                if(board[h][l]!=board[h-1][l-1]){
//                    break;
//                }else{
//                    h--;
//                    l--;
//                    bj++;
//                    if(bj==h-1){
//                        return board[h][l]==1?true:false;
//                    }
//                }
//            }
//
//
//        //上面的都不符合，说明是平局
//        return false;
//    }


//    密码按如下规则进行计分，并根据不同的得分为密码安全等级划分
//
//    一、密码长度
//    5分：小于等于4个字符
//    10分：5-7个字符
//    25分：大于等于8个字符
//
//    二、字母：
//    0分：没有字母
//    10分：密码里字母全是大（小）写
//    20分：密码里字母符合“大小写混合”
//
//    三、数字
//    0分：没有数字
//    10分：1个数字
//    20分：大于1个数字
//
//    五、奖励（只能选符合最多的那种奖励）
//    2分：字母和数字
//    3分：字母、数字、符号
//    5分：大小写字母、数字、符号
//
//    评分标准及对应输出
//    >=90:非常安全 VERY_SECURE
//    >=80:安全 SECURE
//    >=70:非常强 VERY_STRONG
//    >=60:强 STRONG
//    >=50:一般 AVERAGE
//    >=25:弱 WEAK
//    >=0:非常弱 VERY_WEAK
//    public static void main(String[] args) {//通过
//        Scanner scanner=new Scanner(System.in);
//        String str=scanner.nextLine();
//        int bj1=0,bj2=0,bj3=0,bj4=0,bj5=0;//分别对应5种得分标准
//
//        if(str.length()<=4){
//            bj1=5;
//        }else if(5<=str.length()&&str.length()<=7){
//            bj1=10;
//        }else{
//            bj1=25;
//        }
//
//        int tmp1=0,tmp2=0,tmp3=0,tmp4=0;//标记大小字母、数字、符号的个数
//
//        for(int i=0;i<str.length();i++){
//            //大写字母
//            if(65<=str.charAt(i)&&str.charAt(i)<=90){
//                tmp1++;
//            }
//            //小写字母
//            else if(97<=str.charAt(i)&&str.charAt(i)<=122) {
//                tmp2++;
//            }
//            //数字
//            else if(48<=str.charAt(i)&&str.charAt(i)<=57){
//                tmp3++;
//            }else{//符号
//                tmp4++;
//            }
//        }
//
//        //字母
//        if(tmp1+tmp2==0){//没有字母
//            bj2=0;
//        }else{//有字母
//            if(tmp1==0||tmp2==0){//只有大写或小写
//                bj2=10;
//            }else{//大小写混合
//                bj2=20;
//            }
//        }
//
//        //数字
//        if(tmp3==0){
//            bj3=0;
//        }
//        if(tmp3==1){
//            bj3=10;
//        }
//        if(tmp3>1){
//            bj3=20;
//        }
//
//        //符号
//        if(tmp4==0){
//            bj4=0;
//        }
//        if(tmp4==1){
//            bj4=10;
//        }
//        if(tmp4>1){
//            bj4=25;
//        }
//
//        //奖励
//        if(bj2==10&&bj3!=0){
//            bj5=2;
//        }
//        if(bj2==10&&bj3!=0&&tmp4!=0){
//            bj5=3;
//        }
//        if(bj2==20&&bj3!=0&&tmp4!=0){
//            bj5=5;
//        }
//
//        int sum=bj1+bj2+bj3+bj4+bj5;
//
//        if(sum>=90){
//            System.out.println("VERY_SECURE");
//        }
//        if(sum>=80&&sum<90){
//            System.out.println("SECURE");
//        }
//        if(sum>=70&&sum<80){
//            System.out.println("VERY_STRONG");
//        }
//        if(sum>=60&&sum<70){
//            System.out.println("STRONG");
//        }
//        if(sum>=50&&sum<60){
//            System.out.println("AVERAGE");
//        }
//        if(sum>=25&&sum<50){
//            System.out.println("WEAK");
//        }
//        if(sum>=0&&sum<25){
//            System.out.println("VERY_WEAK");
//        }
//
//    }

    //4.1
//    将一棵无穷大满二叉树的节点按根节点一层一层地从左往右编号，根节点编号为1。
//    现给定a、b两个结点，设计一个算法，返回a、b最近的公共祖先编号。
//    注意：其祖先也可能是节点本身
//
//    eg:输入2，3
//    返回1

    //标准答案：
//    public int getLCA(int a, int b) {
//        if(a==b){
//            return a;
//        }else{
//            while(a!=b){
//                if(a>b){
//                    a=a/2;
//                }else{//a<b
//                    b=b/2;
//                }
//            }
//            //由子节点找父节点公式:parent=child/2
//        }
//        return a;
//    }


//    求一个int类型数字对应的二进制数字中1的最大连续数，例如3的二进制位00000011，最大连续2个1
//    数据范围：数据组数1<=t<=5,1<=n<=500000
//    进阶：时间复杂度O（logn),空间复杂度：O（1）
//
//    输入描述：输入一个int类型数字
//    输出描述：输出转换成二进制后连续1的个数
//
//    eg:
//    输入：200
//    输出：2
//
//    说明：200的二进制表示是11001000，最多有2个连续的1

    //标准答案
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        while(scanner.hasNext()){
//            int n=scanner.nextInt();
//            int count=0;
//            int max=0;
//
//            while(n!=0){
//                if((n&1)==1){//n末位为1
//                    //&:按位与——对应二进制位全1为1，有0为0
//                    //eg:
//                    //a=10，对应二进制0000 1010
//                    //b=1， 对应二进制0000 0001
//                    //          a&b=0000 0000
//                    count++;
//                    if(count>max){
//                        max=count;
//                    }
//                }else{//n末位为0
//                    if(count>max){
//                        max=count;
//                    }
//                    count=0;
//                }
//                n>>=1;
//            }
//            System.out.println(max);
//        }
//    }


    //4.3
//    任意一个偶数（大于2）都可以由2个素数组成，组成偶数的2个素数有很多种情况，
//    本题要求输出组成指定偶数的两个素数差值最小的素数对。
//
//    数据范围：输入的数据满足4<=n<=1000
//
//    输入描述：输入一个大于2的偶数
//    输出描述：从小到大的两个素数
//
//    示例1:
//    输入20
//    输出7 13
//
//    示例2：
//    输入4
//    输出2 2


    //判断是不是素数-通过
//    public static boolean isSs(int x){
//        //素数——除了1和它本身没有其他数可以整除
//        if(x==0||x==1){
//            return false;
//        }
//        for(int i=2;i<x;i++){
//            if(x%i==0){
//                return false;
//            }
//        }
//        return true;
//    }
//    //找小于n的 素数差值最小 素数对
//    public static void func(int n){
//        int min=n;//表示素数对最小差值,这里赋值n只是为了后面比较时可以直接把tmp放进去
//        ArrayList<Integer> arrayList=new ArrayList<>();//存放素数
//        for(int i=2;i<n;i++){//1不是素数，我们这里节约资源 素数判断从2开始
//            if(isSs(i)&&isSs(n-i)){//能放入的都是一对能组成n的数
//                arrayList.add(i);
//            }
//        }
//        int x=0;//标记最小素数对中较小者的下标
//        int y=0;//arraylist长度
//        if(arrayList.size()%2==0){
//            y=arrayList.size();
//        }else{//arraylist.size为什么会等于奇数？除了一对一对进来的，还有可能是本身，就比如118，它的素数对还有59和59
//            y=arrayList.size()+1;
//        }
//        for(int i=0;i<y/2;i++){
//            //y里面都是能构成n的对
//            //y/2就是有几对符合构成n的素数，
//            if(n-arrayList.get(i)-arrayList.get(i)<min){
//                min=n-arrayList.get(i)-arrayList.get(i);
//                x=i;
//            }
//        }
//        System.out.println(arrayList.get(x));
//        System.out.println(n-arrayList.get(x));
//    }
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        int n=scanner.nextInt();
//        func(n);
//    }


    //给定两个32位整数n和m，同时给定i和j，
    //将m的二进制数位插入到n的二进制的第j到第i位，保证n的第j到第i位均为0，
    //且m的二进制数小于等于i-j+1，其中二进制的位数从0开始由低到高

    //测试样例：1024,19,2,6
    //返回：1100

    //标准答案：


    //4.4
    //小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3...
    //这条石板路要根据特殊的规则才能前进：对于小易当前所在编号为k的石板，
    //小易单次只能往前跳k的一个约数（不含1和k）步，即跳到k+x（x为k的一个非1和本身的约数）的位置
    //小易当前处在编号为N的石板，他想跳到编号恰好为M的石板上去，小易想知道最少需要跳跃几次可以到达

    //例如：N=4，M=24
    //4->6->8->12->18->24
    //于是小易最少需要跳跃5次，就可以从4号石板跳到24号石板

    //输入描述：输入为1行，有两个整数N,M，以空格隔开（4<=N<=100000）,N<=M<=100000
    //输出描述：输出小易最少需要跳跃的步数，如果不能达到输出-1

    //示例1:
    //输入：4  24
    //输出：5


//法1：递归，但是遇到较大的数运算会超时
//    public static int func(int x,int y){//从x到y要几步
//        if(x==y){
//            return 0;
//        }
//        int min=0;
//        int count=0;
//        for(int i=2;i<x;i++){//这里N的约数不包含1和N
//            if(x%i==0){
//                if(x+i<=y){
//                    int tmp=x+i;
//                    count=func(tmp,y)+1;
//                }else{
//                    break;//当前的格子加上i已经过了终点了，而你不可能走负数格子（约数不包含负数）
//                }
//            }
//            min=count;//标记最小次数
//            if(count<min){
//                min=count;
//            }
//        }
//        return min;
//    }
//
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        int N=scanner.nextInt();
//        int M=scanner.nextInt();
//        int x=func(N,M);
//        System.out.println(x);
//
//    }

    //法2：非递归（标准答案）
//    public static List<Integer> div(int num){//约数
//        List<Integer> list=new ArrayList<Integer>();
//        for(int i=2;i*i<=num;i++){//约数不能是1或本身
//            if(num%i==0){//i是约数
//                list.add(i);
//                if(num/i!=i){
//                    //i是约数，说明num/i也是约数，比如12的约数有3和4
//                    //但是num/i!=i,比如16的约数4，你不能放2个4进去
//                    list.add(num/i);
//                }
//            }
//        }
//        return list;
//    }
//
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        int n=scanner.nextInt();
//        int m=scanner.nextInt();
//        int[]step=new int[m+1];//m+1是因为m块石板，我们为了让石板下标和编号对应
//        for(int i=0;i<m+1;i++){//初始化
//            step[i]=Integer.MAX_VALUE;//表示没有到过这块石板的记录路线
//        }
//        step[n]=0;
//        for(int i=n;i<m;i++){//i代表当前石板编号
//            if(step[i]==Integer.MAX_VALUE){//无法跳跃到该位置
//                continue;
//            }
//            List<Integer> list=div(i);//求i的约数集合（不包含1和本身）
//            //j代表1次可以跳几块石板
//            for(int j:list){//遍历除1和本身的所有约数
//                if(i+j<=m&&step[i+j]!=Integer.MAX_VALUE){//之前有过到这个石板的路线记录了
//                    step[i+j]=Math.min(step[i+j],step[i]+1);
//                    //假设之前有跳到i+j上的石板路径次数为4，
//                    //而跳到i上的次数为2，那么我现在i到i+J是2+1=3次，
//                    //那么新的最小次数就是step[i]+1
//                }else if(i+j<=m){//之前没有过到这个石板的路线记录了
//                    step[i+j]=step[i]+1;
//                }
//            }
//        }
//        if(step[m]==Integer.MAX_VALUE){//跳不到这个石板上
//            System.out.println(-1);
//        }else{
//            System.out.println(step[m]);
//        }
//    }


    //day14 4.12
    //计算日期到天数的转换
    //根据输入的日期，计算是这一年的第几天
    //保证年份为4位数，且日期合法
    //输入描述：输入一行，每行空格分割，分别是年，月，日
    //输出描述：输出是这一年的第几天

    //示例1:
    //输入：2012 12 31
    //输出：366

    //示例2：
    //输入1982 3 4
    //输出63
//    public static void main(String[] args) {//通过
//        Scanner scanner=new Scanner(System.in);
//        int y=scanner.nextInt();
//        int m=scanner.nextInt();
//        int d=scanner.nextInt();
//        boolean flg=false;//标记是不是闰年
//
//        if(m>=2){
//            //判断是不是闰年
//            if(y%4==0&&y%100!=0){
//                flg=true;
//            }
//            if(y%400==0){
//                flg=true;
//            }
//        }
//
//        int sum=0;//统计天数
//        for(int i=1;i<m;i++){//第m个月后面加
//            switch (i){
//                case 1:
//                case 3:
//                case 5:
//                case 7:
//                case 8:
//                case 10:
//                case 12:
//                    sum+=31;
//                    break;
//                case 2:
//                    if(flg==true){
//                        sum+=29;
//                    }else{
//                        sum+=28;
//                    }
//                    break;
//                case 4:
//                case 6:
//                case 9:
//                case 11:
//                    sum+=30;
//                    break;
//            }
//        }
//        sum+=d;
//        System.out.println(sum);
//    }


    //幸运的袋子
    //一个袋子里有n个球，每个球上面都有一个号码（拥有相同号码的球是无区别的）
    //如果一个袋子是幸运的，当且仅当所有球的号码和大于所有球的号码积

    //例如：如果袋子里面的球号码是{1,1,2,3},这个袋子就是幸运的，因为1+1+2+3>1*1*2*3
    //你可以适当从袋子里移除一些球（可以移0个，但是别都移完），要使移除后的袋子是幸运的。
    //现让你编程计算一下你可以获得多少种不同的幸运的袋子

    //输入描述：
    //第一行输入一个正整数n（n<=1000）
    //第二行为n个正整数Xi（Xi<=1000）

    //输出描述：输出可以产生的幸运的袋子数

    //输入：3
    //     1 1 1

    //输出：2


    //球号码和-通过10%
//    public static int sum(int[]arr,int x){//arr从后往前x个不计数
//        int count=0;
//        for(int i=0;i<arr.length-x;i++){
//            count+=arr[i];
//        }
//        return count;
//    }
//    //球号码乘积
//    public static int c(int[]arr,int x){
//        int count=1;
//        for(int i=0;i<arr.length-x;i++){
//            count*=arr[i];
//        }
//        return count;
//    }
//
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        int n=scanner.nextInt();
//
//        HashMap<Integer,Integer> hashMap=new HashMap();
//        int[]arr=new int[n];
//
//        for(int i=0;i<n;i++){
//            arr[i]=scanner.nextInt();
////            if(hashMap.containsKey(arr[i])){//设置相同球值出现的次数
////                int j=hashMap.get(arr[i]);//获取对应value，也就是之前有过几个相同的球
////                hashMap.put(arr[i],j+1);
////            }else{
////                hashMap.put(arr[i],1);
////            }
//        }
//        Arrays.sort(arr);//对数组进行排序(升序)
//        int count=0;
//        //不移走球，看是否是幸运的袋子
//        if(sum(arr,0)>c(arr,0)){
//            count++;
//        }
//
//        for(int i=1;i<=n-2;i++){//你最多移走n-2个球（留下2个来做相加运算和相乘运算）
////            for(int j=n-1;j>=0;j++){//要移走球，你肯定要从大的开始移
////
////            }
//            if(sum(arr,i)>c(arr,i)){
//                count++;
//            }
//        }
//        System.out.println(count);
//    }


    //day15 4.13
    //输入一个正整数，计算它在二进制下1的个数
    //注意多组输入输出！

    //数据范围：1<=n<=2^31-1

    //输入描述：输入一个整数
    //输出描述：计算整数二进制中1的个数

    //示例1：
    //输入5
    //输出2
    //说明：5的二进制表示是101，有2个1

    //示例2：
    //输入0
    //输出0

//    public static void main(String[] args) {//通过
//        Scanner scanner=new Scanner(System.in);
//        while(scanner.hasNext()){
//            long n=scanner.nextLong();
//            long count=0;
//            while(n!=0){
//                if((n&1)==1){
//                    count++;
//                }
//                n=n >> 1;
//            }
//            System.out.println(count);
//        }
//    }


//    public int findMinimum(int n, int[] left, int[] right) {
//
//    }


    //day16
    //完美数（Perfect number）又称完美数或完备数，是一些特殊的自然数。
    //它所有的真因子（即除了自身以外的约束）的和（即因子函数），恰好等于它本身
    //例如：28，它有约束1,2,4,7,14,28 除去它本身28外，其余5个数相加，1+2+4+7+14=28

    //输入n，请输出n以内（含n）完全数的个数

    //数据范围：1<=n<=5*10^5

    //输入描述：输入一个数字n
    //输出描述：输出不超过n的完全数的个数

//    public static boolean ys(int n){//求n的约束和
//        int sum=1;
//        for(int i=2;i<n;i++){//1是任何数的约数，我们直接把它算到sum里了
//            if(n%i==0){
//                sum+=i;
//            }
//        }
//        if(sum==n){
//            return true;
//        }else{
//            return false;
//        }
//
//    }
//    public static void main(String[] args) {//通过
//        Scanner scanner=new Scanner(System.in);
//        int n=scanner.nextInt();
//        int count=0;
//        for(int i=2;i<=n;i++){//因为是要除去本身的，1就不能算了
//            if(ys(i)){
//                count++;
//            }
//        }
//        System.out.println(count);
//    }


//    扑克牌游戏大家应该都比较熟悉了，一副牌由54张组成，含3~A，2各4张，小王1张，大王1张。牌面从小到大用如下字符和字符串表示（其中，小写joker表示小王，大写JOKER表示大王）:)
//            3 4 5 6 7 8 9 10 J Q K A 2 joker JOKER
//    输入两手牌，两手牌之间用“-”连接，每手牌的每张牌以空格分隔，“-”两边没有空格，如：4 4 4 4-joker JOKER
//    请比较两手牌大小，输出较大的牌，如果不存在比较关系则输出ERROR
//
//    基本规则：
//            （1）输入每手牌可能是个子，对子，顺子（连续5张），三个，炸弹（四个）和对王中的一种，不存在其他情况，由输入保证两手牌都是合法的，顺子已经从小到大排列；
//            （2）除了炸弹和对王可以和所有牌比较之外，其他类型的牌只能跟相同类型的存在比较关系（如，对子跟对子比较，三个跟三个比较），不考虑拆牌情况（如：将对子拆分成个子）
//            （3）大小规则跟大家平时了解的常见规则相同，个子，对子，三个比较牌面大小；顺子比较最小牌大小；炸弹大于前面所有的牌，炸弹之间比较牌面大小；对王是最大的牌；
//            （4）输入的两手牌不会出现相等的情况。
//
//    答案提示：
//            （1）除了炸弹和对王之外，其他必须同类型比较。
//            （2）输入已经保证合法性，不用检查输入是否是合法的牌。
//            （3）输入的顺子已经经过从小到大排序，因此不用再排序了.
//
//            数据范围：保证输入合法


    //通过
//    public static int findSpecial(String str){//特殊的手牌
//        String[]arr=str.split(" ");//手牌是用空格分割的，我们这里把空格去掉
//        if(arr.length==2){//对子或者大小王的情况
//            if(arr[0].equals("joker")||arr[1].equals("joker")){
//                //题目中说了，大小王是成对出现的，我们这里只要判断是不是0和1下标是joker即可
//                return 1;//最高优先级
//            }
//        }else if(arr.length==4){//题目中规定4个只有炸弹
//            return 2;//第二优先级
//        }
//        return 3;//其他的都是第三优先级——第三优先级的同类比较
//    }
//
//    public static int size(char x){//单张牌面大小
//        //规定3 4 5 6 7 8 9 10 J  Q  K A  2 大小王成对出现，这里不考虑
//        //对应1 2 3 4 5 6 7  8 9 10 11 12 13
//        if(3<=x&&x<=10){
//            return x-2;
//        }
//        switch (x){
//            case 'J':
//                return 9;
//            case 'Q':
//                return 10;
//            case 'K':
//                return 11;
//            case 'A':
//                return 12;
//        }
//        return 0;
//    }
//
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        String str=scanner.nextLine();
//        String[] arr=str.split("-");//把两手牌用split分割开来
//        String str1=arr[0];
//        String str2=arr[1];
//        int level1=findSpecial(str1);
//        int level2=findSpecial(str2);
//        if(level1==1||level2==1){//有一方出现双王
//            if(level1==1){
//                System.out.println(arr[0]);
//            }else{
//                System.out.println(arr[1]);
//            }
//            return;
//        }else if(level1==2||level2==2){//没有双王，但是有一方有炸弹
//            if(level1==2&&level2==2){//都是炸弹
//                if(arr[0].charAt(0)>arr[1].charAt(0)){
//                    System.out.println(arr[0]);
//                }else{
//                    System.out.println(arr[1]);
//                }
//                return;
//            }
//            if(level1==2||level2==2){//有一方是炸弹，另一方不是
//                if(level1==2){
//                    System.out.println(arr[0]);
//                }else{
//                    System.out.println(arr[1]);
//                }
//                return;
//            }
//        }else{//没有炸弹，没有双王，那就是同类型比较了
//            String[] tmp1=str1.split(" ");//计算第一幅牌的个数
//            String[] tmp2=str2.split(" ");//计算第二幅牌的个数
//            if(tmp1.length!=tmp2.length){//牌个数不一样没法比
//                System.out.println("ERROR");
//            }else{//牌个数一样，个子，对子，三个比较牌面大小；顺子比较最小牌大小
//                //也就是我们比第一张牌即可
//                if(size(str1.charAt(0))>size(str2.charAt(0))){
//                    System.out.println(str1);
//                }else{
//                    System.out.println(str2);
//                }
//            }
//        }
//
//    }


    //day17杨辉三角的变形
    //通过73.3%,如果输入的n比较大会超时
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        int n=scanner.nextInt();
//
//        //由于对称关系，题目要求又是第一个偶数，我们只要把每行的前i个数搞出来就可以了
//        int[][] arr=new int[n][n];//默认里面存放的都是0
//
//        //构造一个n行的杨辉三角变形
//        for(int i=1;i<=n;i++){//n行
//            for(int j=1;j<=i;j++){//每行i个数（只求半个）
//                if(j==1){
//                    arr[i-1][j-1]=1;
//                }else{
//                     if(j<i){
//                        if(j<=2){
//                            arr[i-1][j-1]=arr[i-2][j-1]+arr[i-2][j-2];
//                        }else{//j>=3
//                            arr[i-1][j-1]=arr[i-2][j-1]+arr[i-2][j-2]+arr[i-2][j-3];
//                        }
//                    }else if(j==i){//j=i
//                        if(i==2){
//                            arr[i-1][j-1]=1;
//                        }else{
//                            arr[i-1][j-1]=arr[i-2][j-2]+2*arr[i-2][j-3];
//                        }
//                    }
//
//                }
//                if(i==n&&arr[i-1][j-1]%2==0){
//                    System.out.print(j);
//                    return;
//                }
//            }
//        }
//        System.out.println(-1);//上面整个流程下来没有return说明第i行没有偶数
//    }


    //day18
    //统计每个月兔子的总数
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        int n=scanner.nextInt();
//        if(n==1||n==2){
//            System.out.println(1);
//            return;
//        }
//        int m1=0;//一月大的
//        int m2=0;//两月大的
//        int able=1;//有能力生的（大于三个月了）
//        int count=1;//兔子总数
//        for(int i=3;i<=n;i++){
//            able+=m2;//2给月的长大变成能生的
//            m2=m1;//1个月的长大变成2个月的
//            m1=able;//有能力生的，生出了它自己数量的兔子
//            count=able+m1+m2;
//        }
//        System.out.println(count);
//    }

    //字符串通配符


    //day19 汽水瓶-通过
//    public static int func(int kp){//kp表示空瓶数
//        if(kp<2){
//            return 0;
//        }
//        if(kp==2){
//            return 1;
//        }
//        int qs=kp/3;//兑换产生的汽水
//        kp=kp%3;//余下的空瓶
//        kp+=qs;//余下的空瓶加上兑换产生的空瓶
//        return qs+func(kp);
//    }
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        while(scanner.hasNext()){//多组输入
//            int n=scanner.nextInt();
//            if(n==0){
//                break;
//            }
//            if(n==1){
//                System.out.println(0);
//            }
//            if(n==2){
//                System.out.println(1);//借一个空瓶子，换一瓶汽水，再把空的还了
//            }
//            System.out.println(func(n));
//        }
//    }

    //查找两个字符串a,b中的最长公共子串-通过75%
    //公共子串
//    public static void getMaxLen(String str1,String str2){
//        char[] arr1=str1.toCharArray();//把字符串转换成字符数组
//        char[] arr2=str2.toCharArray();
//        int l1=arr1.length;
//        int l2=arr2.length;
//        int tmp=0;//标记最大子串结束位置
//        int[][] maxSubLen=new int[l1+1][l2+1];
//        int maxLen=0;
//        for(int i=1;i<=l1;i++){
//            for(int j=1;j<=l2;j++){
//                if(arr1[i-1]==arr2[j-1]){
//                    //F(i,j)=F(i-1,j-1)+1
//                    maxSubLen[i][j]=maxSubLen[i-1][j-1]+1;
//
//                    //是否需要更新最大值
//                    if(maxLen<maxSubLen[i][j]){
//                        maxLen=maxSubLen[i][j];
//                        tmp=i;
//                    }
//                }
//            }
//        }
//        for(int i=tmp-maxLen;i<tmp;i++){
//            System.out.print(arr1[i]);
//        }
//    }
//
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        while(scanner.hasNext()){
//            String str1=scanner.nextLine();
//            String str2=scanner.nextLine();
//            getMaxLen(str1,str2);
//        }
//    }


//    public static int getMaxLen(String str1,String str2){
//        char[] arr1=str1.toCharArray();//把字符串转换成字符数组
//        char[] arr2=str2.toCharArray();
//        int l1=arr1.length;
//        int l2=arr2.length;
//        int[][] maxSubLen=new int[l1+1][l2+1];
//        int maxLen=0;
//        for(int i=1;i<=l1;i++){
//            for(int j=1;j<=l2;j++){
//                if(arr1[i-1]==arr2[j-1]){
//                    //F(i,j)=F(i-1,j-1)+1
//                    maxSubLen[i][j]=maxSubLen[i-1][j-1]+1;
//
//                    //是否需要更新最大值
//                    if(maxLen<maxSubLen[i][j]){
//                        maxLen=maxSubLen[i][j];
//                    }
//                }
//            }
//        }
//        return maxLen;
//    }
//
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        String str1=scanner.nextLine();
//        String str2=scanner.nextLine();
//        int x=getMaxLen(str1,str2);
//        System.out.println(x);
//    }


    //day20
    //字符串反转--通过
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        String str=scanner.nextLine();
//        for(int i=str.length()-1;i>=0;i--){
//            System.out.print(str.charAt(i));
//        }
//    }


    //day21
    //洗牌--通过
//    public static void xp(int[]arr,int[]brr){//把arr里的牌洗一遍放到brr中
//        int n=arr.length/2-1;//左手牌
//        int m=arr.length-1;//右手牌
//
//        for(int i=arr.length-1;i>=0;i--){
//            if(i%2!=0){//arr.length-1是奇数，我们最开始是要右手排
//                brr[i]=arr[m];
//                m--;
//            }else{
//                brr[i]=arr[n];
//                n--;
//            }
//        }
//    }
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        int t=scanner.nextInt();
//        for(int a=0;a<t;a++){
//            int n=scanner.nextInt();
//            int k=scanner.nextInt();
//            int[]arr=new int[2*n];
//            int[]brr=new int[2*n];
//            for(int i=0;i<arr.length;i++){
//                arr[i]=scanner.nextInt();
//            }
//            for(int i=0;i<k;i++){//k次洗牌
//                if(i%2==0){
//                    xp(arr,brr);
//                }else{
//                    xp(brr,arr);
//                }
//            }
//            if(k%2==0){
//                for(int i=0;i<arr.length;i++){
//                    System.out.print(arr[i]+" ");
//                }
//            }else{
//                for(int i=0;i<brr.length;i++){
//                    System.out.print(brr[i]+" ");
//                }
//            }
//            System.out.println();
//        }
//    }

    //day22
    //找出字符串中第一次只出现一次的字符-通过
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        String str=scanner.nextLine();
//        HashMap<Character,Integer> hashMap=new HashMap<>();//字符-字符出现了几次
//        char[]arr=new char[str.length()];//字符-第几次出现第一次
//        int k=0;
//        for(int i=0;i<str.length();i++){
//            if(!hashMap.containsKey(str.charAt(i))){
//                hashMap.put(str.charAt(i),1);
//                arr[k]=str.charAt(i);
//                k++;
//            }else{
//                hashMap.put(str.charAt(i),hashMap.get(str.charAt(i))+1);
//            }
//        }
//
//        //遍历arr2
//        for(char x:arr){
//            //根据arr里面的字符顺序遍历，后面还要确认一下是不是这个字符串只出现了一次
//            if(hashMap.containsKey(x)){
//                if(hashMap.get(x)==1){
//                    System.out.println(x);
//                    return;
//                }
//            }
//        }
//        System.out.println(-1);
//    }




    //day23
    //微信红包--通过
//    public static int getValue(int[] gifts, int n) {
//        int l=gifts.length/2;
//        int max=0;
//        HashMap<Integer,Integer> hashMap=new HashMap<>();
//        for(int i=0;i<gifts.length;i++){
//            if(!hashMap.containsKey(gifts[i])){
//                hashMap.put(gifts[i],1);
//            }else{
//                hashMap.put(gifts[i],hashMap.get(gifts[i])+1);
//            }
//        }
//
//        Iterator iterator=hashMap.entrySet().iterator();
//        while(iterator.hasNext()){
//            Map.Entry<Integer,Integer> entry=(Map.Entry<Integer,Integer>)iterator.next();
//            if(entry.getValue()>l){
//                return entry.getKey();
//            }
//        }
//        return 0;
//    }


    //计算字符串的编辑距离
    //标准答案
//    public static int getDistance(String str1,String str2){
//        char[] arr1=str1.toCharArray();
//        char[] arr2=str2.toCharArray();
//        int l1=arr1.length;
//        int l2=arr2.length;
//        //定义一个矩阵
//        int[][]dist=new int[l1+1][l2+1];
//        //初始状态F（0，j）=j（插入）F（i，0）=i（删除）
//        for(int i=0;i<=l1;i++){
//            dist[i][0]=i;
//        }
//        for(int j=0;j<=l2;j++){
//            dist[0][j]=j;
//        }
//        for(int i=1;i<=l1;i++){
//            for(int j=1;j<=l2;j++){
//                //F（i,j）=min{F(i,j-1)+1，F(i-1,j)+1，F(i-1,j-1)+(A[i]==B[j]?0:1)}
//                dist[i][j]=Math.min(dist[i][j-1]+1,dist[i-1][j]+1);
//                if(arr1[i-1]==arr2[j-1]){
//                    dist[i][j]=Math.min(dist[i][j],dist[i-1][j-1]);
//                }else{
//                    dist[i][j]=Math.min(dist[i][j],dist[i-1][j-1]+1);
//                }
//            }
//        }
//        return dist[l1][l2];
//    }
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        String str1=scanner.nextLine();
//        String str2=scanner.nextLine();
//        int x=getDistance(str1,str2);
//        System.out.println(x);
//    }


    //day24
    //迷宫问题
//    public static int func(int i, int j, int[][] arr) {
//        if (i == arr.length-1 && j == arr[0].length-1) {//到终点了
//            return 1;
//        }
//        if (arr[i][j] == 1) {//走不了
//            return 0;
//        } else {//arr[i][j]==0
//            int x=func(i + 1, j, arr);
//            int y=func(i, j + 1, arr);
//            return  x+y;
//        }
//    }
//
//    public static void main(String[] args) {
//
//            Scanner scanner = new Scanner(System.in);
//            int n = scanner.nextInt();
//            int m = scanner.nextInt();
//            int[][] arr = new int[n][m];
//            for(int i=0;i<n;i++){
//                for(int j=0;j<m;j++){
//                    arr[i][j]=scanner.nextInt();
//                }
//            }
//            int x = func(0, 0, arr);
//            System.out.println(x);
//        }


    //day25
    //数根
    //写法1
//    public static int func(int x) {//通过
//        int sum=0;//计算各位和
//        while(x/10!=0){//x不是1位数
//            sum+=x%10;
//            x=x/10;
//        }
//        sum+=x;
//        if(sum/10!=0){
//            sum=func (sum);
//        }
//        return sum;
//    }
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        while(scanner.hasNext()){//多组输入
//            int x=scanner.nextInt();
//            boolean flg=false;
//            if(x/10==0){
//                System.out.println(x);
//                flg=true;
//            }
//
//            if(flg==false){
//                System.out.println(func(x));
//            }
//        }
//    }
    //法二
//        public static void main(String[] args){
//            Scanner scanner=new Scanner(System.in);
//            while(scanner.hasNext()){
//                String str=scanner.next();
//                while(str.length()>1){
//                    int result=0;
//                    for(int i=0;i<str.length();i++)
//                        result+=str.charAt(i)-'0';//把字符串类型的数变成整形
//                    str=String.valueOf(result);//产生新的数再次进行循环
//                }
//                System.out.println(str);
//            }
//        }

    //星际密码
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        while(scanner.hasNext()){
//            int n=scanner.nextInt();
//            int[]arr=new int[n];
//            for(int i=0;i<n;i++){
//                arr[i]=scanner.nextInt();
//            }
//
//        }
//    }

    //day26
    //青蛙跳台阶--通过
//    public int jumpFloorII(int target) {//通过
//        return (int)Math.pow(2,target-1);
//    }

    //快到碗里来--通过
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        while(scanner.hasNext()){
//            double n=scanner.nextDouble();
//            double r=scanner.nextDouble();
//            double c=3.14*2*r;
//            if(n>c){
//                System.out.println("No");
//            }else{
//                System.out.println("Yes");
//            }
//        }
//    }


    //day27
    //求两个数的和，要求不能使用+ - * /
    //参考答案
//    public int Add(int num1,int num2) {
//        int sum=0;
//        int num3=0;
//        while(num2!=0){
//            sum=num1^num2;//^异或,相同为0，相异为1
//            //假设num1=1,num2=2
//            //0000 0001
//            //0000 0010
//            //num1^num2 =0000 0011=3
//            num3=(num1&num2)<<1;
//            num1=sum;
//            num2=num3;
//        }
//        return sum;
//    }


    //三角形
    //通过
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        while(scanner.hasNext()){
//            Double a=scanner.nextDouble();
//            Double b=scanner.nextDouble();
//            Double c=scanner.nextDouble();
//            int flg=0;
//            if((a+b>c)&&(a+c>b)){
//                if(b+c>a){
//                    System.out.println("Yes");
//                    flg=1;
//                }
//            }
//            if(flg==0){
//                System.out.println("No");
//
//            }
//        }
//    }


    //day29
    //求正数数组的最小不可组成和
    //标准答案
//    public int getFirstUnFormedNum(int[] arr) {
//        int min=arr[0];//arr中最小值
//        int max=0;//arr所有元素和
//        for(int i=0;i<arr.length;i++){
//            if(min>=arr[i]){
//                min=arr[i];
//            }
//            max+=arr[i];
//        }
//        int[] res =new int[100001];
//        res[0]=1;
//        for(int i=0;i<arr.length;i++){
//            for(int j=max;j>=0;j--){
//                if(res[j]==1){
//                    res[j+arr[i]]=1;
//                }
//            }
//        }
//        while(min<=max&&res[min]==1){
//            min++;
//        }
//        return min;
//    }


    //有假币
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        double n=scanner.nextDouble();
//
//    }


    //day30
    //最难的问题
    //通过
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        while(scanner.hasNext()){
//            String str=scanner.nextLine();
//            String str2="";
//            for(int i=0;i<str.length();i++){
//                if(str.charAt(i)>='F'&&str.charAt(i)<='Z'){
//                    int a=(int)str.charAt(i)-5;
//                    str2+=(char)a;
//                }else if(str.charAt(i)>='A'&&str.charAt(i)<='E'){
//                    int a=(int)str.charAt(i)+21;
//                    str2+=(char)a;
//                }else{
//                    str2+=str.charAt(i);
//                }
//            }
//            System.out.println(str2);
//        }
//    }


    //因子个数
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        while(scanner.hasNext()){
//
//        }
//    }

    //day31
    //美国节日
    //通过
//    public static boolean isRn(int year) {//判断是不是闰年
//        if(((year%4==0)&&year%100!=0)||(year%400==0)){
//            return true;
//        }
//           return false;
//
//    }
//    public static   int day_of_week(int year, int month, int day)//蔡勒公式，给年月日计算出这天是星期几
//    {
//        if (month == 1 || month == 2)
//        {
//            month += 12;
//            year -= 1;
//        }
//
//        int century = year / 100;
//        year %= 100;
//        int week = year + (year / 4) + (century / 4) - 2 * century + 26 * (month + 1) / 10 + day -
//                1;
//        week = (week % 7 + 7) % 7;
//
//        if (week == 0)
//        {
//            week = 7;
//        }
//
//        return week;
//    }
//
//    public static void printFunc(int y,int m,int d) {
//        String str1="-";
//        String str2="-";
//        boolean f1=false;
//        boolean f2=false;
//        if(m/10==0){
//            f1=true;
//            str1+=0;
//        }
//        if(d/10==0){
//            f2=true;
//            str2+=0;
//        }
//        System.out.println(y + str1 + m + str2 + d);
//    }
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        while (scanner.hasNext()) {
//            int y = scanner.nextInt();
//            boolean f=isRn(y);
//            for (int m = 1; m <= 12; ) {
//                    int x = 0;
//                    if (m % 2 == 0) {//偶数月
//                        if (m == 2) {
//                            if (f) {
//                                x = 29;
//                            } else {
//                                x = 28;
//                            }
//                        } else {
//                            x = 30;
//                        }
//                    } else {
//                        x = 31;
//                    }
//                    int tmp=day_of_week(y,m,1);//这年这月第一天是星期几
//                    boolean flg=false;//后面用于标记劳动节的
//                    for (int d = 1; d <= x; d++) {
//                        int j=(d+tmp)/7+1;//第几个星期
//                        // 注意，第几个星期！=第几个星期几
//                        //比如你这个月是星期4是1号，那你第一个星期3，是第二个星期才出现的
//
//                        int w = day_of_week(y,m,d);//这年这月这日是星期几
//                        //蔡勒公式，给一个年月日计算是星期几
//
//                        if ((m == 1 && d == 1) || (m == 7 && d == 4) || (m == 12 && d == 25)) {//指定节日
//                            if(m<10){
//                                System.out.println(y + "-0" + m + "-0" + d);
//                            }else{
//                                System.out.println(y + "-" + m + "-" + d);
//                            }
//                            continue;
//                        } else if (m == 1  && w == 1) {//马丁路德金纪念日
//                            if(1<tmp){
//                                //比如你这个月是星期3是1号，那你第三个星期1,是第四个星期才出现的
//                                if(4==j){
//                                    printFunc(y,m,d);
//                                }
//                            }else{//这个月第一天就是星期1，那第三个星期1，就是第三个星期出现
//                                if(3==j){
//                                    printFunc(y,m,d);
//                                }
//                            }
//                        } else if (m == 2  && w == 1) {//总统节
//                            if(1<tmp){
//                                if(4==j){
//                                    printFunc(y,m,d);
//                                }
//                            }else{
//                                if(3==j){
//                                    printFunc(y,m,d);
//                                }
//                            }
//                        } else if (m == 5  && w == 1) {//阵亡将士纪念日
//                            //五月第一天是星期一，最后一个星期一是在 第5个星期
//                            //五月第一天是星期日，最后一个星期一是在 第6个星期
//                            int k=0;
//
//                            for(int a=0;a<7;a++){
//                                if (flg==true){
//                                    break;
//                                }
//                                if(day_of_week(y,5,31-a)==1){
//                                    printFunc(y,m,31-a);
//                                    flg=true;
//                                }
//                            }
//                        } else if (m == 9 && w == 1) {//劳动节
//                            if(1<tmp){
//                                if(2==j){
//                                    printFunc(y,m,d);
//                                }
//                            }else{
//                                if(1==j){
//                                    printFunc(y,m,d);
//                                }
//                            }
//                        } else if (m == 11 && w == 4) {//感恩节
//                            if(4<tmp){
//                                if(5==j){
//                                    printFunc(y,m,d);
//                                }
//                            }else{
//                                if(4==j){
//                                    printFunc(y,m,d);
//                                }
//                            }
//                        }
//                    }
//                    m++;
//                }
//
//            System.out.println();
//        }
//    }

    //分解因数


    //day31
    //淘宝网店

//    public static int  month(int year,int month) {//判断这年这个月共多少天
//        if (month == 2) {
//            //判断年是不是闰年
//            if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)) {
//                return 29;
//            } else {
//                return 28;
//            }
//        } else if (month == 4 || month == 6 || month == 9 || month == 11) {
//            return 30;
//        } else {
//            return 31;
//
//        }
//    }
//
//    public static int func(int m) {//判断这个月是不是素数月，每天能拿多少钱
//        //素数月有2，3，5，7，11
//        int x=0;
//        if (m == 2 || m == 3 || m == 5 || m == 7 || m == 11) {//素数月赚1快
//            x = 1;
//        } else {
//            x = 2;
//        }
//        return x;
//    }
//        public static void main (String[]args){
//            Scanner scanner = new Scanner(System.in);
//            while (scanner.hasNext()) {
//                int y1 = scanner.nextInt();
//                int m1 = scanner.nextInt();
//                int d1 = scanner.nextInt();
//
//                int y2 = scanner.nextInt();
//                int m2 = scanner.nextInt();
//                int d2 = scanner.nextInt();
//
//                int sum = 0;//标记赚的钱
//
//                if (y1 - y2 == 0) {//同一年
//                    for (int m = m1; m <= m2; m++) {
//                        int x = func(m);
//                        if (m1 != m2) {
//                            if (m == m1) {//第一月
//                                sum += (month(y1, m1) - d1 + 1) * x;
//                            } else if (m > m1 && m < m2) {//中间月
//                                sum += month(y1, m) * x;
//                            } else {//最后一月
//                                sum += d2 * x;
//                            }
//                        } else {
//                            sum += (d2 - d1 + 1) * x;
//                        }
//
//                    }
//                } else {//不同年
//                    for (int m = m1; m <= 12; m++) {//第一年
//                        int x = func(m);
//                        if (m == m1) {
//                            sum += (month(y1, m1) - d1 + 1) * x;
//                        } else {
//                            sum += month(y1, m) * x;
//                        }
//                    }
//
//                    if (y2 - y1 > 1) {
//                        int tmpYear = y1 + 1;
//                        while (tmpYear < y2) {
//                            for (int m = 1; m <= 12; m++) {
//                                int x = func(m);
//                                sum += month(tmpYear, m)*x;
//                            }
//                            tmpYear++;
//                        }
//                    }
//
//                    for (int m = 1; m < m2; m++) {//最后一年
//                        int x = func(m);
//
//                        sum += month(y2, m) * x;
//                    }
//                    int x = func(m2);
//                    sum += d2*x;
//                }
//                System.out.println(sum);
//            }
//
//        }
    //斐波那契凤尾


    //day33
    //剪花布条

    //客似云来
    //参考答案
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        while(scanner.hasNext()){
//            int from=scanner.nextInt();
//            int to=scanner.nextInt();
//            int[] arr=new int[100];
//            arr[0]=1;
//            arr[1]=1;
//            int sum=0;
//            //第i天的人数是斐波那契数列，a[i]=a[i-1]+a[i-2]
//            if(to>2){
//                for(int i=2;i<to;i++){
//                    arr[i]=arr[i-1]+arr[i-2];
//                }
//            }
//            for(int i=from-1;i<to;i++){
//                sum+=arr[i];
//            }
//            System.out.println(sum);
//        }
//    }


    //day34
    //养兔子
    //通过
    //这种经过一段时间1个多带一个的题目可以用斐波那契数列做
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        while(scanner.hasNext()){
//            int n=scanner.nextInt();
//            long[]arr=new long[91];
//            arr[1]=1;
//            arr[2]=2;
//            for(int i=3;i<=90;i++){
//                arr[i]=arr[i-1]+arr[i-2];
//            }
//            System.out.println(arr[n]);
//        }
//    }
    //收件人列表
    //通过
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        while(scanner.hasNext()){
//            int n=scanner.nextInt();
//            scanner.nextLine();//把回车那个吃了
//            String[]str=new String[n];
//            for(int i=0;i<n;i++){
//                str[i]=scanner.nextLine();
//                if(str[i].contains(" ")||str[i].contains(",")){
//                    str[i]="\""+str[i]+"\"";
//                }
//                if(i!=n-1){
//                    System.out.print(str[i]+",");
//                }else{
//                    System.out.println(str[i]);
//                }
//            }
//
//        }
//    }

    //day37
    //数据库连接池

    //mkdir
    //参考答案
//        public static void main(String[] args) {
//            Scanner scanner = new Scanner(System.in);
//            while (scanner.hasNext()) {
//                int n = Integer.parseInt(scanner.nextLine());
//                String[] str = new String[n];
//                for (int i = 0;i<n;i++) {
//                    str[i] = scanner.nextLine();
//                }
//                Arrays.sort(str);
//                List<String> list = new ArrayList<>();
//                for (int i = 1;i<n;i++) {
//                    if (!str[i].startsWith(str[i-1] +"/")) {
//                        list.add(str[i-1]);
//                    }
//                }
//                list.add(str[n-1]);
//                for (int i = 0;i<list.size();i++) {
//                    System.out.println("mkdir -p " +list.get(i));
//                }
//                System.out.println();
//            }
//        }



    //day38
    //红与黑
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        while(scanner.hasNext()){
//            int m=scanner.nextInt();
//            int n=scanner.nextInt();
//            if(m==0&&n==0){
//                System.out.println(0);
//                return;
//            }
//            char[][] arr=new char[20][20];//地板，arr里面放". # @"
//            int[][] brr=new int[20][20];//标记是否已访问
//            int[][]crr=new int[4][2];
//            int x=0,y=0;//起始位置坐标
//
//            for(int i=0;i<m;i++){
//                for(int j=0;j<n;j++){
//
//                }
//            }
//        }
//    }
    //蘑菇阵


    //day39
    //字符串计数
    //参考答案
//    public static long get(String str1,String str2,int min){
//        long suma=0;
//        long sumb=0;
//        char[] arr=str1.toCharArray();
//        char[] brr=str2.toCharArray();
//        for(int i=0;i< arr.length;i++){
//            suma+=(arr[i]-'a')*(long)Math.pow(26,min-1-i);
//        }
//        if(arr.length!=0){
//            suma++;
//        }
//        for(int i=0;i<brr.length;i++){
//            sumb+=(brr[i]-'a')*(long)Math.pow(26,min-1-i);
//        }
//        if(brr.length!=0){
//            suma++;
//        }
//        return sumb-suma;
//    }
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        while(scanner.hasNext()){
//            String s=scanner.nextLine();
//            String[]arr=s.split(" ");
//            int min =Integer.parseInt(arr[2]);
//            int max =Integer.parseInt(arr[3]);
//            long sum=0;
//            for(int i=min;i<max;i++){
//                char a=arr[0].charAt(0);
//                char b=arr[1].charAt(0);
//                sum+=(long)Math.pow(26,i-1)*(b-a);
//                String la=arr[0].substring(1,i<arr[0].length()?i:arr[0].length());
//                String lb=arr[1].substring(1,i<arr[1].length()?i:arr[1].length());
//                sum+=get(la,lb,i-1);
//            }
//            long tmp=sum-1;
//            System.out.println(tmp%1000007);
//        }
//    }

    //最长公共子序列
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String str1 = scanner.nextLine().toLowerCase();
            String str2 = scanner.nextLine().toLowerCase();
            System.out.println(findLCS(str1, str1.length(), str2, str2.length()));
        }
    }

    public static int findLCS(String A, int n, String B, int m) {
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = 0;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
                }
            }
        }
        return dp[n][m];
    }
}








